import numpy as np
class Point:
    def __init__(self,x,y) -> None:
        self.x=x
        self.y=y
    def is_lu(self,other):
        if self.x<=other.x and self.y>=other.y:
            return True
        return False
    def is_ru(self,other):
        if self.x>=other.x and self.y>=other.y:
            return True
        return False
    def is_rd(self,other):
        if self.x>=other.x and self.y<=other.y:
            return True
        return False
    def is_ld(self,other):
        if self.x<=other.x and self.y<=other.y:
            return True
        return False
    def __add__(self,other):
        return Point(self.x+other.x,self.y+other.y)
    def __lt__(self, other):
        return self.x < other.x or self.x == other.x and self.y < other.y
    def __gt__(self, other):
        return self.x > other.x or self.x == other.x and self.y > other.y
    def __le__(self, other):
        return self.x <= other.x or self.x == other.x and self.y <= other.y
    def __ge__(self, other):
        return self.x >= other.x or self.x == other.x and self.y >= other.y
    def __eq__(self,other):
        return self.x == other.x and self.y == other.y
class Rect:
    def __init__(self,p1:Point,p2:Point) -> None:
        self.p1=p1
        self.p2=p2
    def __add__(self, other):
        left=min(self.p1.x,other.p1.x)
        right=max(self.p2.x,other.p2.x)
        bottom=min(self.p1.y,other.p1.y)
        top=max(self.p2.y,other.p2.y)
        return Rect(Point(left,bottom),Point(right,top))
    def add(self,other):
        return self.__add__(self,other)
    @property
    def width(self):
        return self.p2.x-self.p1.x
    @property
    def center(self):
        return Point((self.p1.x+self.p2.x)//2,(self.p1.y+self.p2.y)//2)
    @property
    def height(self):
        return self.p2.y-self.p1.y
    @property
    def area(self):
        return self.width*self.height
    def __lt__(self, other):
        return self.p1 < other.p1 or self.p1 == other.p1 and self.p2 < other.p2
    def __gt__(self, other):
        return self.p1 > other.p1 or self.p1 == other.p1 and self.p2 > other.p2
    def __le__(self, other):
        return self.p1 <= other.p1 or self.p1 == other.p1 and self.p2 <= other.p2
    def __ge__(self, other):
        return self.p1 >= other.p1 or self.p1 == other.p1 and self.p2 >= other.p2
    def __eq__(self,other):
        if other==None:
            return False
        return self.p1 == other.p1 and self.p2 == other.p2
    def extend(self,ratio,_min=(0,0),_max=(4999,4999)):#HxW
        extend_x=int(ratio[0]*self.width)
        extend_y=int(ratio[1]*self.height)
        p1=Point(max(_min[1],self.p1.x-extend_x),max(_min[0],self.p1.y-extend_y))
        p2=Point(min(self.p2.x+extend_x,_max[1]),min(self.p2.y+extend_y,_max[0]))
        return Rect(p1,p2)
    def extend_abs(self,lens,_min=(0,0),_max=(4999,4999)):
        extend_x=int(lens[0])
        extend_y=int(lens[1])
        p1=Point(max(_min[1],self.p1.x-extend_x),max(_min[0],self.p1.y-extend_y))
        p2=Point(min(self.p2.x+extend_x,_max[1]),min(self.p2.y+extend_y,_max[0]))
        return Rect(p1,p2)
    def rect_and(self,other):
        if is_rectangle_overlap(self,other)==False:
            return None
        return Rect(Point(max(self.p1.x,other.p1.x),max(self.p1.y,other.p1.y)),Point(min(self.p2.x,other.p2.x),min(self.p2.y,other.p2.y)))

def is_rectangle_overlap(rectangle1, rectangle2):
    # 检查X轴方向上是否有重叠
    if rectangle1.p1.x > rectangle2.p2.x or rectangle2.p1.x > rectangle1.p2.x:
        return False
    # 检查Y轴方向上是否有重叠
    if rectangle1.p1.y > rectangle2.p2.y or rectangle2.p1.y > rectangle1.p2.y:
        return False
    # 如果两个方向上都有重叠，则返回True
    return True
class Block:
    def __init__(self,p1:Point,p2:Point,bid) -> None:
        self.p1=p1
        self.p2=p2
        self.rect=Rect(self.p1,self.p2)
        self.left_adj=[]
        self.right_adj=[]
        self.top_adj=[]
        self.bottom_adj=[]
        self.sub_blocks=[]
        self.bid=bid#block编号
        self.cid=None#对应裂缝编号
    def get_hori_range(self):
        return (self.p1.x,self.p2.x)
    def get_vert_range(self):
        return (self.p1.y,self.p2.y)
    def get_adj_num(self):
        return len(self.left_adj)+len(self.right_adj)+len(self.bottom_adj)+len(self.top_adj)
    def get_adj(self):
        return self.left_adj+self.right_adj+self.bottom_adj+self.top_adj
    def get_rect(self):
        return self.rect
    def disconnect(self,other_bid):
        if other_bid in self.left_adj:
            self.left_adj.remove(other_bid)
        if other_bid in self.right_adj:
            self.right_adj.remove(other_bid)
        if other_bid in self.bottom_adj:
            self.bottom_adj.remove(other_bid)
        if other_bid in self.top_adj:
            self.top_adj.remove(other_bid)
        pass
    def __lt__(self, other):
        return self.rect<other.rect
    def __gt__(self, other):
        return self.rect>other.rect
    def __le__(self, other):
        return self.rect<=other.rect
    def __ge__(self, other):
        return self.rect>=other.rect
    def __eq__(self,other):
        if other==None:
            return False
        return self.rect==other.rect
    def __hash__(self):
        return hash(self.p1.x)^hash(self.p1.y)^hash(self.p2.x)^hash(self.p2.y)
def istouch(interval1,interval2):
    return max(interval1[0],interval2[0])<= min(interval1[1],interval2[1])
def merge(interval1,interval2):
    assert istouch(interval1,interval2)
    left=min(interval1[0],interval2[0])
    right=max(interval1[1],interval2[1])

    return (left,right)
class Crack:
    def __init__(self,blocks,cid,bbox=None) -> None:
        self.cid=cid
        self.blocks=blocks#Blcok class
        if bbox==None:
            bbox=blocks[0].get_rect()
            for block in blocks:
                bbox=bbox+block.get_rect()
        self.bound=bbox
    def rect(self):
        return self.bound
    def merge(self,other):
        cid=self.cid
        blocks=self.blocks+other.blocks
        bbox=self.bound+other.bound
        return Crack(blocks,cid,bbox)
def get_cluster_feature(blocks,viewport):
    lu_count=0
    ru_count=0
    rd_count=0
    ld_count=0
    for block in blocks:
        if block.get_rect().center.is_lu(viewport.center):
            lu_count+=1
        elif block.get_rect().center.is_ru(viewport.center):
            ru_count+=1
        elif block.get_rect().center.is_rd(viewport.center):
            rd_count+=1
        elif block.get_rect().center.is_ld(viewport.center):
            ld_count+=1
        else :
            assert(0)
    block_count=lu_count+ru_count+rd_count+ld_count
    feature=(lu_count/block_count,ru_count/block_count,rd_count/block_count,ld_count/block_count)
    return feature
class Cluster:
    def __init__(self,blocks,feature,viewport:Rect) -> None:
        self.blocks=blocks
        self.viewport=viewport#rect
        self.feature=feature#lu,ru,rd,ld
    def __eq__(self,other):
        if other==None:
            return False
        return self.viewport==other.viewport
    def area(self):
        return self.viewport.area
    def rect(self):
        return self.viewport
    def __hash__(self):
        return hash(self.viewport.p1.x)^hash(self.viewport.p1.y)^hash(self.viewport.p2.x)^hash(self.viewport.p2.y)
    def check_merge(self,other):
        cur_center=self.viewport.center
        other_center=other.viewport.center
        if is_rectangle_overlap(self.rect(),other.rect())==True:
            return True
        if cur_center.x<=other_center.x and cur_center.y<=other_center.y:
            if self.feature[1]>0.25 and other.feature[2]>0.25:
                return True
        elif cur_center.x<=other_center.x and cur_center.y>=other_center.y:
            if self.feature[3]>0.25 and other.feature[0]>0.25:
                return True
        elif cur_center.x>=other_center.x and cur_center.y<=other_center.y:
            if self.feature[0]>0.25 and other.feature[3]>0.25:
                return True
        elif cur_center.x>=other_center.x and cur_center.y>=other_center.y:
            if self.feature[2]>0.25 and other.feature[1]>0.25:
                return True
        return False
    def merge(self,other):
        blocks=self.blocks+other.blocks
        viewport=self.viewport+other.viewport
        feature=get_cluster_feature(blocks,viewport)
        return Cluster(blocks,feature,viewport)
class BackBone:
    def __init__(self,blocks) -> None:
        self.blocks=blocks
def get_dist(p1:Point,p2:Point):
    return np.sqrt(np.square(p1.x-p2.x)+np.square(p1.y-p2.y))



        

